class BiTreeNode:
    def __init__(self, data):
        self.data = data
        self.lchild = None
        self.rchild = None


a = BiTreeNode('A')
b = BiTreeNode('B')
c = BiTreeNode('C')
d = BiTreeNode('D')
e = BiTreeNode('E')
f = BiTreeNode('F')
g = BiTreeNode('G')

e.lchild = a
e.rchild = g
a.rchild = c
c.lchild = b
c.rchild = d
g.rchild = f

root = e

"""
前序遍历，中序遍历，后序遍历都是深度优先
"""


# 前序遍历，前序序列
def pre_order(root):
    if root:
        print(root.data, end='')
        pre_order(root.lchild)
        pre_order(root.rchild)


# 中序遍历，中序序列
def in_order(root):
    if root:
        in_order(root.lchild)
        print(root.data, end='')
        in_order(root.rchild)


# 后序遍历，后序序列
def post_order(root):
    if root:
        post_order(root.lchild)
        post_order(root.rchild)
        print(root.data, end='')


# 层序遍历
from collections import deque


def level_order(root):
    q = deque()
    q.append(root)
    while (len(q) > 0):  # 队不空时循环
        x = q.popleft()
        print(x.data, end='')
        if x.lchild:
            q.append(x.lchild)
        if x.rchild:
            q.append(x.rchild)


level_order(root)


